#include "phylip.h"
#include "dist.h"
#include <math.h>
#include <iomanip>
#include <string>
#include <cassert>
#include <iostream>
/* version 3.6. (c) Copyright 1993-2004 by the University of Washington.
   Written by Joseph Felsenstein, Akiko Fuseki, Sean Lamont, and Andrew Keeffe.
   Permission is granted to copy and use this program provided no fee is
   charged for it and provided that this copyright notice is not removed. */

using std::string;
using std::vector;
void coordinates(node *p, double lengthsum, long *tipy, double *tipmax,
				 node *start)
{
	// establishes coordinates of nodes //
	node *q, *first, *last;

	if ( p->tip )
	{
		p->xcoord = (long)(over * lengthsum + 0.5);
		p->ycoord = *tipy;
		p->ymin = *tipy;
		p->ymax = *tipy;
		(*tipy) += down;
		if ( lengthsum > *tipmax )
			*tipmax = lengthsum;
		return;
	}
	q = p->next;
	do
	{
		if ( q->back )
			coordinates(q->back, lengthsum + q->v, tipy,tipmax, start);
		q = q->next;
	} while ( (p == start || p != q) && (p != start || p->next != q) );
	first = p->next->back;
	q = p;
	while ( q->next != p && q->next->back )	 // is this right ? //
		q = q->next;
	last = q->back;
	p->xcoord = (long)(over * lengthsum + 0.5);
	if ( p == start )
		p->ycoord = p->next->next->back->ycoord;
	else
		p->ycoord = (first->ycoord + last->ycoord) / 2;
	p->ymin = first->ymin;
	p->ymax = last->ymax;
}  // coordinates //


void drawline(std::ostream& os, long i, double scale, node *start, bool rooted, unsigned spp,
				const vector<string>& nayme)
{
	// draws one row of the tree diagram by moving up tree //
	node *p, *q;
	unsigned n=0;
	bool extra=false, trif=false;
	node *r, *first =NULL, *last =NULL;
	bool done=false;

	p = start;
	q = start;
	extra = false;
	trif = false;
	if ( i == (long)p->ycoord && p == start )
	{  // display the root //
		if ( rooted )
		{
			if ( p->index - spp >= 10 )
				os << "-";
			else
				os << "--";
		}
		else
		{
			if ( p->index - spp >= 10 )
				os << " ";
			else
				os << "  ";
		}
		if ( p->index - spp < 10 )
			os << '-';
		os << p->index - spp;
		extra = true;
		trif = true;
	}
	else
		os << "  ";
	do
	{
		if ( !p->tip )
		{ // internal nodes //
			r = p->next;
			// r->back here is going to the same node. //
			do
			{
				if ( !r->back )
				{
					r = r->next;
					continue;
				}
				if ( i >= r->back->ymin && i <= r->back->ymax )
				{
					q = r->back;
					break;
				}
				r = r->next;
			} while ( !((p != start && r == p) || (p == start && r == p->next)) );
			first = p->next->back;
			r = p;
			while ( r->next != p )
				r = r->next;
			last = r->back;
			if ( !rooted && (p == start) )
				last = p->back;
		} // end internal node case... //
		// draw the line: //
		done = (p->tip || p == q);
		n = (long)(scale * (q->xcoord - p->xcoord) + 0.5);
		if ( !q->tip )
		{
			if ( (n < 3) && (q->index - spp >= 10) )
				n = 3;
			if ( (n < 2) && (q->index - spp < 10) )
				n = 2;
		}
		if ( extra )
		{
			n--;
			extra = false;
		}
		if ( (long)q->ycoord == i && !done )
		{
			if ( p->ycoord != q->ycoord )
				os << "+";
			if ( trif )
			{
				n++;
				trif = false;
			}
			if ( !q->tip )
			{
				for (unsigned j = 1; j <= n - 2; j++ )
					os << "-";
				if ( q->index - spp < 10 )
					os << '-';
				os << q->index - spp;
				extra = true;
			}
			else
			{
				for (unsigned j = 1; j < n; j++ )
					os << '-';
			}
		}
		else if ( !p->tip )
		{
			if ( (long)last->ycoord > i && (long)first->ycoord < i
				 && i != (long)p->ycoord )
			{
				os << '!';
				for (unsigned j = 1; j < n; j++ )
					os << ' ';
			}
			else
			{
				for (unsigned j = 1; j <= n; j++ )
					os << ' ';
				trif = false;
			}
		}
		if ( q != p )
			p = q;
	} while ( !done );
	if ( (long)p->ycoord == i && p->tip )
	{
		os << nayme[p->index - 1];
	}
	os << "\n";
}  // drawline //


void printree(std::ostream& os, node *start, bool rooted, unsigned spp,
			const vector<string>& nayme)
{
	// prints out diagram of the tree //
	// used in fitch & neighbor //
	long tipy;
	double scale,tipmax;

	os << "\n";
	tipy = 1;
	tipmax = 0.0;
	coordinates(start, 0.0, &tipy, &tipmax, start);
	scale = 1.0 / (long)(tipmax + 1.000);
	for (int i = 1; i <= (tipy - down); i++ )
		drawline(os, i, scale, start, rooted, spp, nayme);
	os << "\n";
}  // printree //


void tree_to_nh_strm(std::ostream& os, node *p, node *start, const vector<string>& nayme)
{
	// write out file with representation of final tree //
	// used in fitch & neighbor //
	if ( p->tip )
		os << nayme[p->index - 1];
	else
	{
		os << '(';
		tree_to_nh_strm(os, p->next->back, start, nayme);
		os << ',';
		tree_to_nh_strm(os, p->next->next->back, start, nayme);
		if ( p == start)
		{
			os << ',';
			tree_to_nh_strm(os, p->back,  start, nayme);
		}
		os << ')';
	}
	if ( p == start )
		os << ";";
	else
		os << std::fixed << std::setprecision(5) << ":" << p->v;
}  // tree_to_nh_strm //
